{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Consecutive Values You Can Make"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMaximumConsecutive"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #你能构造出连续值的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>coins</code> ，它代表你拥有的 <code>n</code> 个硬币。第 <code>i</code> 个硬币的值为 <code>coins[i]</code> 。如果你从这些硬币中选出一部分硬币，它们的和为 <code>x</code> ，那么称，你可以 <strong>构造</strong> 出 <code>x</code> 。</p>\n",
    "\n",
    "<p>请返回从 <code>0</code> 开始（<strong>包括</strong> <code>0</code> ），你最多能 <strong>构造</strong> 出多少个连续整数。</p>\n",
    "\n",
    "<p>你可能有多个相同值的硬币。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>coins = [1,3]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>你可以得到以下这些值：\n",
    "- 0：什么都不取 []\n",
    "- 1：取 [1]\n",
    "从 0 开始，你可以构造出 2 个连续整数。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>coins = [1,1,1,4]\n",
    "<b>输出：</b>8\n",
    "<strong>解释：</strong>你可以得到以下这些值：\n",
    "- 0：什么都不取 []\n",
    "- 1：取 [1]\n",
    "- 2：取 [1,1]\n",
    "- 3：取 [1,1,1]\n",
    "- 4：取 [4]\n",
    "- 5：取 [4,1]\n",
    "- 6：取 [4,1,1]\n",
    "- 7：取 [4,1,1,1]\n",
    "从 0 开始，你可以构造出 8 个连续整数。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,4,10,3,1]\n",
    "<b>输出：</b>20</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>coins.length == n</code></li>\n",
    "\t<li><code>1 <= n <= 4 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= coins[i] <= 4 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-consecutive-values-you-can-make](https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-consecutive-values-you-can-make](https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]', '[1,1,1,4]', '[1,4,10,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        left, right = 0, 0\n",
    "        for coin in coins:\n",
    "            x, y = left + coin, right + coin\n",
    "            if(x > right + 1):\n",
    "                break\n",
    "            else:\n",
    "                right += coin\n",
    "        return right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        m = 0\n",
    "        for c in coins:\n",
    "            if c > m + 1: break \n",
    "            m += c \n",
    "        return m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        x = 0\n",
    "        for i, c in enumerate(coins):\n",
    "            if(c <= x+1):\n",
    "                x += c\n",
    "        return x+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        now=1\n",
    "        coins.sort()\n",
    "        for i in coins:\n",
    "            if i>now:\n",
    "                break\n",
    "            now+=i\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        left, right = 0, 0\n",
    "        for coin in coins:\n",
    "            x, y = left + coin, right + coin\n",
    "            if(x > right + 1):\n",
    "                break\n",
    "            else:\n",
    "                right += coin\n",
    "        return right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        m = 0\n",
    "        for i in coins:\n",
    "            if i>m+1: break\n",
    "            else:\n",
    "                m+=i\n",
    "        return m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, c: List[int]) -> int:\n",
    "        a, b = 0, 0\n",
    "        c.sort()\n",
    "        for j in c:\n",
    "            d = a + j\n",
    "            e = b + j\n",
    "            if d>(b+1):\n",
    "                return b+1 \n",
    "            else:\n",
    "                b = e\n",
    "        return b+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        n = len(coins)\n",
    "        need = 1\n",
    "        for x in coins:\n",
    "            if x > need:\n",
    "                return need\n",
    "            need += x\n",
    "        return need\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        m = 0  # 一开始只能构造出 0\n",
    "        coins.sort()\n",
    "        for c in coins:\n",
    "            if c > m + 1:  # coins 已排序，后面没有比 c 更小的数了\n",
    "                break  # 无法构造出 m+1，继续循环没有意义\n",
    "            m += c  # 可以构造出区间 [0,m+c] 中的所有整数\n",
    "        return m + 1  # [0,m] 中一共有 m+1 个整数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "\n",
    "        max_ = 0\n",
    "        for i, c in enumerate(coins):\n",
    "            if c > max_ + 1:\n",
    "                break\n",
    "            else:\n",
    "                max_ = c + max_\n",
    "        \n",
    "        return max_ + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        now = 0\n",
    "        for coin in coins:\n",
    "            if coin > now + 1:\n",
    "                return now + 1\n",
    "            else:\n",
    "                now += coin\n",
    "        return now + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        tmp=[0]\n",
    "        al=sum(coins)+1\n",
    "        l=0\n",
    "        now=1\n",
    "        coins.sort()\n",
    "        for i in coins:\n",
    "            if i<=now:\n",
    "                now+=i\n",
    "            else:\n",
    "                break\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        ans = 1\n",
    "        for i in coins:\n",
    "            if i > ans:\n",
    "                return ans\n",
    "            ans += i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\r\n",
    "        coins.sort()\r\n",
    "        cur = 0 \r\n",
    "        for x in coins:\r\n",
    "            if x > cur + 1:\r\n",
    "                break\r\n",
    "            cur = cur + x \r\n",
    "        return cur + 1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        m = 0 # 一开始只能构造出0\n",
    "        coins.sort()\n",
    "        for c in coins:\n",
    "            if c > m + 1: # coins已排序，后面没有比c更小的数\n",
    "                break # 无法构造出m + 1， 继续循环没有意义\n",
    "            m += c # 可以构造出区间[0, m + c] 中的所有整数\n",
    "        return m + 1 # [0, m] 中一共有m + 1各整数\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        m = 0\n",
    "        for c in coins:\n",
    "            if c>m+1:\n",
    "                break\n",
    "            m += c\n",
    "        return m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        m = 0  # 一开始只能构造出 0\n",
    "        coins.sort()\n",
    "        for c in coins:\n",
    "            if c > m + 1:  # coins 已排序，后面没有比 c 更小的数了\n",
    "                break  # 无法构造出 m+1，继续循环没有意义\n",
    "            m += c  # 可以构造出区间 [0,m+c] 中的所有整数\n",
    "        return m + 1  # [0,m] 中一共有 m+1 个整数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        left, right = 0, 0\n",
    "        for coin in coins:\n",
    "            x, y = left + coin, right + coin\n",
    "            if(x > right + 1):\n",
    "                break\n",
    "            else:\n",
    "                right += coin\n",
    "        return right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        m=1\n",
    "        coins.sort()\n",
    "        for i in range(0,len(coins)):\n",
    "            if coins[i]>m:\n",
    "                break\n",
    "            else:\n",
    "                m=m+coins[i]\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        x = 0\n",
    "        for y in coins:\n",
    "            if y > x + 1:\n",
    "                break\n",
    "            x += y\n",
    "        return x + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "#中等题\n",
    "[官方题解](https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make/solutions/2090079/ni-neng-gou-zao-chu-lian-xu-zhi-de-zui-d-wci4/)\n",
    "'''\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        ans = 0\n",
    "        for c in coins:\n",
    "            if  (c -1) <= ans:\n",
    "                ans = c + ans\n",
    "            else:\n",
    "                return ans +1\n",
    "\n",
    "        return ans +1\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        res = 1\n",
    "        for i in sorted(coins):\n",
    "            if i > res:\n",
    "                break\n",
    "            res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        curr_range=0\n",
    "        for c in coins:\n",
    "            if c > curr_range+1:\n",
    "                break\n",
    "            curr_range += c\n",
    "        return curr_range+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        m = 0\n",
    "        coins.sort()\n",
    "        for c in coins:\n",
    "            if c > m + 1:\n",
    "                break\n",
    "            m += c\n",
    "        return m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        threshold = sum(coins)\n",
    "        res = 1\n",
    "        for c in coins:\n",
    "            if c > res:\n",
    "                break\n",
    "            res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()  # 对硬币数组进行排序\n",
    "        \n",
    "        curr_max = 0  # 初始化可以构造的连续整数的最大值为0\n",
    "        for coin in coins:\n",
    "            if coin <= curr_max + 1:\n",
    "                curr_max += coin\n",
    "            else:\n",
    "                break  # 如果当前硬币不能用于构造连续整数，中断循环\n",
    "        \n",
    "        # 返回可以构造的连续整数的数量，这是curr_max + 1\n",
    "        return curr_max + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        m = 0  # 一开始只能构造出 0\n",
    "        coins.sort()\n",
    "        for c in coins:\n",
    "            if c > m + 1:  # coins 已排序，后面没有比 c 更小的数了\n",
    "                break  # 无法构造出 m+1，继续循环没有意义\n",
    "            m += c  # 可以构造出区间 [0,m+c] 中的所有整数\n",
    "        return m + 1  # [0,m] 中一共有 m+1 个整数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        # 原来如此\n",
    "        m = 0\n",
    "        coins.sort()\n",
    "        for c in coins:\n",
    "            if c > m + 1:\n",
    "                break\n",
    "            m += c \n",
    "        return m + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        x = 0\n",
    "        for y in coins:\n",
    "            if y >x+1:\n",
    "                break\n",
    "            x+= y \n",
    "        return x +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        # 首先对coins排序\n",
    "        # 假设0...m已经可以连续构造出，那么当前的c，如果c>m+1, 那么m+1是构造不出来的，那么只能到m\n",
    "        # 否则的话，能够构造出的最大数，更新为m+c，且由于0到m都有了，那么m+1到m+c的所有数也有了\n",
    "        coins.sort()\n",
    "        m = 0\n",
    "        for c in coins:\n",
    "            if c>m+1:\n",
    "                break\n",
    "            m += c\n",
    "        return m+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        now = 0\n",
    "        coins.sort()\n",
    "        for x in coins:\n",
    "            if x > now + 1:\n",
    "                return now + 1\n",
    "            now += x\n",
    "        return now + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins = sorted(coins)\n",
    "        ans = 1\n",
    "        for i in coins:\n",
    "            if i <= ans: ans += i\n",
    "            else: break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        #copy zero\n",
    "        coins.sort()\n",
    "        x = 0\n",
    "        for y in coins:\n",
    "            if y >x+1:\n",
    "                break\n",
    "            x+= y \n",
    "        return x +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        ma = 0\n",
    "        coins.sort()\n",
    "        for coin in coins:\n",
    "            if coin<=ma+1:\n",
    "                ma += coin\n",
    "            else:\n",
    "                break\n",
    "        return ma+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins = sorted(coins)\n",
    "        ans = 1\n",
    "        for i in coins:\n",
    "            if i <= ans:\n",
    "                ans += i\n",
    "            else: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        L = 0\n",
    "        R = 0\n",
    "\n",
    "        for num in coins:\n",
    "            La = L + num\n",
    "            Ra = R + num\n",
    "            \n",
    "            if R+1>=La:\n",
    "                R = Ra\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        res = R-L+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        coins.sort()\n",
    "        upper = 0\n",
    "        for num in coins:\n",
    "            if num>upper+1:\n",
    "                break\n",
    "            upper += num\n",
    "        return upper+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        now=1\n",
    "        coins.sort()\n",
    "        for i in coins:\n",
    "            if i>now:\n",
    "                break\n",
    "            now+=i\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        # 动态规划问题\n",
    "        coins.sort()\n",
    "        SUM = 0 # 靠计算和\n",
    "        if coins[0] == 1:\n",
    "             SUM += 1\n",
    "        else:\n",
    "            return SUM + 1\n",
    "        for coin in coins[1:]:\n",
    "            if 0 < coin <= SUM + 1: \n",
    "                SUM += coin\n",
    "            else:\n",
    "                return SUM + 1\n",
    "        return SUM + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMaximumConsecutive(self, coins: List[int]) -> int:\n",
    "        ans = 1\n",
    "        for c in sorted(coins):\n",
    "            if c > ans:\n",
    "                break\n",
    "            ans += c \n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
